﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;

namespace BubbleSort
{
	class Program
	{
		/// <summary>
		/// 冒泡排序时间复杂度：O(n)-O(n2)  其中n2表示n的2次方
		/// </summary>
		/// <param name="args"></param>
		static void Main(string[] args)
		{
			//2次比较
			for (int i = 1; i <= 2; i++)
			{
				List<int> list=new List<int>();
				//随机选择1000个数到数组中
				for (int j = 0; j < 100; j++)
				{
					Thread.Sleep(j);
					list.Add(new Random((int) DateTime.Now.Ticks).Next(0,1000));
				}
				Console.WriteLine("\n第"+i+"次比较：");
				Stopwatch watch=new Stopwatch();
				watch.Start();
				var result = list.OrderBy(single => single).ToList();
				watch.Stop();
				Console.WriteLine("\n快速排序耗费时间："+watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是："+string.Join(",",result.Take(10).ToList()));
				watch.Start();
				result = BubbleSort(list);
				watch.Stop();
				Console.WriteLine("\n冒泡排序耗费时间：" + watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是：" + string.Join(",", result.Take(10).ToList()));
			}
			Console.ReadLine();
		}

		public static List<int> BubbleSort(List<int> list )
		{
			int temp;
			//外面的一层循环，总共要比较的次数，比如个数为n，则次数为n-1
			for (int i = 0; i < list.Count-1; i++)
			{
				//取数据中最后一个数的下标，然后从后往前进行对比，从后往前的下标一定大于从前往后的下标
				for (int j = list.Count-1; j > i; j--)
				{
					//如果后面那个数比前面那个数小，两者就做交换操作
					if(list[j]<list[j-1])
					{
						temp = list[j];
						list[j] = list[j - 1];
						list[j - 1] = temp;
					}
				}
			}
			return list;
		}
	}
}
